package com.atguigu.huffmancode;

import com.sun.xml.internal.ws.api.pipe.ContentType;
import sun.security.action.PutAllAction;

import javax.print.attribute.standard.NumberUp;
import java.util.*;

/**
 * @author shkstart
 * @create 2021-08-17 16:23
 */
public class huffmanCode {
    public static void main(String[] args) {
        String content = "i like like like java do you like a java";
        byte[] contentBytes = content.getBytes();
        System.out.println(contentBytes.length);
//        byte[] huffmanZip = huffmanZip(contentBytes);
//        System.out.println(Arrays.toString(huffmanZip)+"长度="+huffmanZip.length);

        /*List<Node> nodes = getNodes(contentBytes);
        System.out.println(nodes);
        System.out.println("哈夫曼树");
        Node huffmanTree = createHuffmanTree(nodes);
        System.out.println("前序遍历");
        huffmanTree.preOrder();
//        StringBuilder hello1 = new StringBuilder("hello");
//        System.out.println(hello1);
//        hello1.append("11");
//        System.out.println(hello1);
//        getCodes(huffmanTree,"",stringBuilder);
        Map<Byte, String> huffmanCodes = getCodes(huffmanTree);
        System.out.println("生成的哈夫曼编码表="+huffmanCodes);
        byte[] huffmanCodeBytes = zip(contentBytes, huffmanCodes);
        System.out.println(Arrays.toString(huffmanCodeBytes));*/
        String byteToBitString = byteToBitString(true, (byte) 1);
        System.out.println(byteToBitString);
    }

    //将一个字节数组的byte转化为二进制的字符串

    /**
     *
     * @param flag 判断是否需要补充高位
     * @param b 传入的字节
     * @return 二进制的字符串
     */
    private static String byteToBitString(boolean flag, byte b) {
        //存储字节
        int temp=b;
        //如果是正数，需要补高位
        if (flag){
            temp|=256;//按位与运算
            /*|=是按位或分配运算符。它采用LHS的当前值（按位或RHS），并将该值分配回LHS（以+=与加法相似的方式）。

         例如：

     foo = 32;   // 32 =      0b00100000
     bar = 9;    //  9 =      0b00001001
     baz = 10;   // 10 =      0b00001010
     foo |= bar; // 32 | 9  = 0b00101001 = 41
            // now foo = 41
     foo |= baz; // 41 | 10 = 0b00101011 = 43
            // now foo = 43*/
        }
        String str = Integer.toBinaryString(temp);//十进制的数字转化为二进制的字符串
        //如果正确，只需要返回前面8位字节
        if (flag){
            return str.substring(str.length()-8);
        }else {
            return str;
        }
    }
    //封装所有过程，一个方法全部到位

    /**
     *
     * @param bytes 字符串的字节数组
     * @return 返回一个数字的字节数组
     */
    public static byte[] huffmanZip(byte[] bytes){
        //步骤一：将一个字节数组转化为一个集合，便于遍历字符出现的次数，加权
        List<Node> nodes = getNodes(bytes);
        //步骤二：根据集合nodes创建哈夫曼树
        Node huffmanTree = createHuffmanTree(nodes);
        //步骤三：根据哈夫曼树生成哈夫曼编码
        Map<Byte, String> huffmanCodes = getCodes(huffmanTree);
        //步骤四：根据生成的哈夫曼编码压缩得到哈夫曼字节数组
        byte[] huffmanCodeBytes = zip(bytes, huffmanCodes);
        return huffmanCodeBytes;


    }
    //将字符串的字节数组转化为数字的字节数组

    /**
     *
     * @param bytes 传入的字节数组
     * @param huffmanCodes 闯入的哈夫曼表
     */
    private static byte[] zip(byte[] bytes,Map<Byte,String> huffmanCodes){
        //创建StringBuilder
        StringBuilder stringBuilder = new StringBuilder();
        //遍历字符，添加对应的编码
        for (byte b:bytes){
            stringBuilder.append(huffmanCodes.get(b));
        }
        //将长串字符改成字节数组，节省内存
        //判断字符串的长度
        int len=0;
        //判断字符串是否可以整除
        if (stringBuilder.length()%8==0){
            len=stringBuilder.length()/8;
        }else {
         len=stringBuilder.length()/8+1;
        }
        //字节数组的索引
        int index=0;
        //创建一个字节数组
        byte[] huffmanCodeBytes = new byte[len];
        for (int i=0;i<stringBuilder.length();i=i+8){
            //临时字符串
            String strByte;
            if (i+8>stringBuilder.length()){
                strByte=stringBuilder.substring(i);

            }else {
                strByte=stringBuilder.substring(i,i+8);
            }
            //字符串转化为字节数组
            huffmanCodeBytes[index]=(byte) Integer.parseInt(strByte,2);
            index++;
        }
        return huffmanCodeBytes;

//        System.out.println(stringBuilder.toString());
    }
    //为了方便，重载getCodes

    private static Map<Byte,String> getCodes(Node root){
        if (root==null){
            return null;
        }
        //向左转移
        getCodes(root.left,"0",stringBuilder);
        //向右转移
        getCodes(root.right,"1",stringBuilder);
        return huffmanCodes;
    }
    //创建hashmap,储存对应的字符编码
    static HashMap<Byte,String> huffmanCodes=new HashMap<Byte,String>();
    //创建拼接的字符串
    static StringBuilder stringBuilder=new StringBuilder();
    private static void getCodes(Node node,String code,StringBuilder stringBuilder){
        //拼接字符
        StringBuilder stringBuilder2 = new StringBuilder(stringBuilder);
        //添加字符
        stringBuilder2.append(code);
        //循环查找,当前节点不为空
        if (node!=null){
            //当前节点的字符data若是为空，那就是非叶子节点，若是不为空，那就是叶子节点
            if (node.data==null){
                //向左排查,左为0，右为1
                getCodes(node.left,"0",stringBuilder2);
                //向右排查
                getCodes(node.right,"1",stringBuilder2);
            }else {
                //若是到了叶子节点，那就储存到hashmap
                huffmanCodes.put(node.data,stringBuilder2.toString());
            }
        }
    }
    //前序遍历的方法
    private static void preOrder(Node root){
        if (root!=null){
            root.preOrder();
        }else {
            System.out.println("是空树，无法遍历");
        }
    }

    //创建哈夫曼树
    private static Node createHuffmanTree(List<Node> nodes){
        //只留一个
        while (nodes.size()>1){
            //排序
            Collections.sort(nodes);
            //输出
//            System.out.println("nodes="+nodes);
            //得到第一和第二个节点
            Node nodeleft = nodes.get(0);
            Node noderight = nodes.get(1);
            //创建一个新的节点存储,没有新的字符，只有权值
            Node parent = new Node(null, nodeleft.weight + noderight.weight);
            parent.left=nodeleft;
            parent.right=noderight;
            //删除，增加
            nodes.remove(nodeleft);
            nodes.remove(noderight);
            nodes.add(parent);
        }
        //返回最后一个节点
        return nodes.get(0);
    }
    //接收字符数组
    private static List<Node> getNodes(byte[] bytes){
        //创建一个list集合
       List<Node> nodes = new ArrayList<>();
       //创建一个map键值对，存储字符和数据
        HashMap<Byte, Integer> counts = new HashMap<>();
        //统计字符的个数，将数据添加到map
        for (byte b:bytes){
            Integer count = counts.get(b);
            if (count==null){
                counts.put(b,1);
            }else {
                counts.put(b,count+1);
            }
        }
        //遍历map,将map值加载到集合
        for (Map.Entry<Byte, Integer> entry:counts.entrySet()){
            nodes.add( new Node(entry.getKey(), entry.getValue()));
        }
        return nodes;
    }
}


//创建Node,存储待数据和权值
class Node implements Comparable<Node>{
   Byte data;//存储字符
    int weight;//权值，也就是字符出现的频率
    //左右节点
    Node left;
    Node right;

    public Node(Byte data, int weight) {
        this.data = data;
        this.weight = weight;
    }

    @Override
    public String toString() {
        return "Node{" +
                "data=" + data +
                ", weight=" + weight +
                '}';
    }

    @Override
    public int compareTo(Node o) {
        return this.weight-o.weight;
    }
    //前序遍历
    public void preOrder(){
        System.out.println(this);
        if (this.left!= null){
            this.left.preOrder();
        }
        if (this.right!=null){
            this.right.preOrder();
        }
    }
}